/*
 * Copyright 北京航空航天大学  @ 2015 版权所有
 */
package com.buaa.edu.leetcode.algorithm.stack;

import java.util.Stack;

/**
 * <p>
 * 给定一个二维0-1矩阵计算包含1的最大面积
 * </p>
 * @author towan
 * @email tongwenzide@163.com
 * 2015年5月24日
 */
public class MaximalRectangle {

    public int maximalRectangle(char[][] matrix) {
        int m = matrix.length;
        if(m==0){
            return 0;//只有0行
        }
        int n = matrix[0].length;
        Stack<Integer> bars = new Stack<Integer>();
        int [][]height = new int[m][n];
        int max = 0;
        for(int j = 0;j<n;j++){
            int h = 0;
            for(int i=0;i<m;i++){
                if(matrix[i][j] =='1'){
                    h++;
                }else{
                    h = 0;//否则就断了
                }
                height[i][j] = h;
            }
        }
        //和之前一样计算最大四方形
        bars.add(-1);//为了方便计算相对距离
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                int prev = bars.peek();
                if(prev<0 || height[i][j]>=height[i][prev]){
                    //压入上升序列下标
                    bars.add(j);
                }else{//一旦下降就计算柱子的面积
                    prev = bars.pop();
                    max = Math.max(max, height[i][prev]*(j-bars.peek()-1));
                    j--;//还不能确定当前元素是否在上升序列之中
                }
            }
            //计算还没计算的上升序列的值
            while(bars.peek()!=-1){
                int prev = bars.pop();
                max = Math.max(max, height[i][prev]*(n-bars.peek()-1));
            }
        }
        return max;
    }
    public static void main(String[] args) {
        char[][] matrix = {{'1','0'}};
        MaximalRectangle maximalRectangle = new MaximalRectangle();
        System.out.println(maximalRectangle.maximalRectangle(matrix));
    }
}
